package com.wpp.algorithm.lagou.part1.lesson1;

import java.util.Stack;

/**
 * @author wpp25
 * @date 2021/4/14 22:25
 * @description：
 *  Leetcode 1021 https://leetcode-cn.com/problems/remove-outermost-parentheses/
 *  栈
 *  给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。
 *
 * 对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。
 */
public class Part1_2_1 {

    public static void main(String[] args) {
        System.out.println(fun("(()())(())"));
    }

    private static String fun(String str) {
        char[] chars = str.toCharArray();
        StringBuilder sb = new StringBuilder();
        String result = "";

        int optIndex = 0;

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < chars.length; i++) {
            sb.append(chars[i]);
            if ('(' == chars[i]) {
                stack.push(chars[i]);
            } else {
                stack.pop();
            }
            if (stack.empty()) {
                result += sb.substring(optIndex + 1,i);
                optIndex = i + 1;
            }
        }
        return result;
    }

}
